package BackTrack.万诺;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/*
    1小时
 */
public class 复原IP地址93 {
    @Test
    public void test() {
//        System.out.println("RES:" + restoreIpAddresses("25525511135"));
        System.out.println("RES:" + restoreIpAddresses("11@11"));
    }

    String S;
    List<String> res = new ArrayList<>();
    StringBuilder tmp = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        S = s;
        bT(0, 0);
        return res;
    }

    private boolean AllAreNum_and_bt0to255_and_WuQianDao0(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] > '9' || chars[i] < '0') {
                return false;
            }
        }

        int num = Integer.parseInt(s);
        if (num < 0 || num > 255) {
            return false;
        }

        // 不能有前导0 .001
        if (s.length() >= 2) {
            for (int i = 0; i < s.length() - 1; i++) {
                if (Integer.parseInt(chars[i] + "") == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private void bT(int cI, int step) {
        if (step == 4) {
            if (cI == S.length()) {
                // 不能直接删tmp 会干扰回溯 越界
                String TMP = new String(tmp);
                res.add(TMP.substring(0, TMP.length() - 1));
            }
            return;
        }

        // 固定3次循环 不用for自己fff
        // if是针对 sub  [ 不是 f参数 参数必须超到n
        if (cI + 1 <= S.length()) {
            String one = S.substring(cI, cI + 1);
            if (AllAreNum_and_bt0to255_and_WuQianDao0(one)) {
                tmp.append(one + ".");
                bT(cI + 1, step + 1);
                tmp.delete(tmp.length() - 2, tmp.length());
            }
        }
        if (cI + 2 <= S.length()) {
            String two = S.substring(cI, cI + 2);
            if (AllAreNum_and_bt0to255_and_WuQianDao0(two)) {
                tmp.append(two + ".");
                bT(cI + 2, step + 1);
                tmp.delete(tmp.length() - 3, tmp.length());
            }
        }
        if (cI + 3 <= S.length()) {
            String three = S.substring(cI, cI + 3);
            if (AllAreNum_and_bt0to255_and_WuQianDao0(three)) {
                tmp.append(three + ".");
                bT(cI + 3, step + 1);
                tmp.delete(tmp.length() - 4, tmp.length());
            }
        }
    }
}
